package com.kehao.leetcode.middle.tree_graph;

import org.junit.Test;

public class BuildTreeByPreOrderAndInOrderSolution {


    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder,0,preorder.length,inorder,0,inorder.length);
    }

    public TreeNode buildTree(int[] preorder,int preLeft,int preRight, int[] inorder,int inLeft,int inRight) {
        if(preLeft>=preRight) return null;
        if(inLeft>=inRight) return null;


        TreeNode root = new TreeNode(preorder[preLeft]);
        int indexOfRoot = 0;//根节点中序遍历的位置
        for (int i = inLeft; i < inRight; i++) {
            if(preorder[preLeft]==inorder[i]){
                indexOfRoot = i;
                break;
            }
        }
        int leftChildLength = indexOfRoot-inLeft;
        root.left = buildTree(preorder,preLeft+1,preLeft+1+leftChildLength,inorder,inLeft,indexOfRoot);
        root.right = buildTree(preorder,preLeft+1+leftChildLength,preRight,inorder,indexOfRoot+1,inRight);
        return root;
    }

    @Test
    public void test01(){
        int[] preorder =  {3,9,20,15,7};
        int[] inorder =  {9,3,15,20,7};
        TreeNode treeNode = buildTree(preorder, inorder);
        System.out.println(treeNode);

    }
}
